补图（complement graph）：在图论中，给定一个（通常指简单无向图）\(G=(V,E)\)，它的补图 \(\overline{G}\) 具有相同的顶点集 \(V\)，并且对任意两个不同顶点 \(u,v\)，当且仅当 \(uv\notin E\) 时，\(\overline{G}\) 中存在边 \(uv\)。直观地说：把原图中没有连边的点对都连起来，把已有的边都去掉。（通常不考虑自环与重边。）
/kmplmnt rf/; /kmplmnt rf/
The complement graph has an edge wherever the original graph does not.
补图会在原图没有边的地方补上一条边。
In many proofs, we analyze a graph and its complement graph to compare clique and independent set properties.
在许多证明中，我们会同时分析一个图及其补图，以比较团（clique）与独立集（independent set）的性质。
complement 源自拉丁语 complementum，含义是“补足、补充”；在数学里引申为“对某个结构取缺失的部分”。graph 源自希腊语 graphein（“书写、描绘”），在现代数学中指用点和边来“画出/表示”关系的结构。因此 complement graph 字面可理解为“把图中缺的关系补全后得到的图”。
Select Language